#pragma once

#include "decision.h"
#include <vector>
#include <list>

namespace solver
{

	class literal_node
	{
	public:

		literal_node *parent;
		literal lit;
		std::list<literal_node *> children;
		int string_id;
		bool used;

		literal_node()
		{
			;
		}

		literal_node( literal_node *_parent, literal _lit, int _string_id ) 
			: parent( _parent ),
			lit( _lit ),
			string_id( _string_id ),
			used(false)
		{
			;
		}

		~literal_node()
		{
			;
		}

		decision_string to_string()
		{
			decision_string ds;
			literal_node *p = this;
			while (p->parent != nullptr)
			{
				ds.push_back(p->lit);
				p = p->parent;
			}
			ds.sort();
			return ds;
		}
	};


	class decision_string_collection
	{
		int string_id;
		literal_node *root;

		struct node_target {
			literal_node *child;
			int index;
		};

		bool find_strings(literal_node *n, const decision_string& ds, int index, int max_index, std::list<literal_node *>& found_strings)
		{
			bool result = false;

			if (index >= max_index) 
			{
				return result;
			}

			std::list<node_target> found_children;

			for (auto& child : n->children)
			{
				int search_index = index;
				literal target = ds[search_index];

				while (child->lit.ref > target.ref) 
				{
					search_index++;
					if (search_index < max_index)
					{
						target = ds[search_index];
					}
					else 
					{
						break;
					}
				}

				if (child->lit.matches(target))
				{
					node_target tg;
					tg.child = child;
					tg.index = search_index;
					found_children.push_back(tg);
				}
			}

			if (found_children.size() > 0)
			{
				for (auto& found_child : found_children)
				{
					if (found_child.child->string_id)
					{
						found_strings.push_back(found_child.child);
						result = true;
					}
					else
					{
						bool tempResult = find_strings(found_child.child, ds, found_child.index + 1, max_index, found_strings);
						if (tempResult)
						{
							result = true;
						}
					}
				}
			}

			return result;
		}

		int add(literal_node *n, const decision_string& ds, int index, int max_index)
		{
			int result = 0;
			if (index >= max_index)
			{
				string_id++;
				n->string_id = string_id;
				return string_id;
			}
			const literal& target = ds[index];
			bool found = false;
			for (auto& child : n->children)
			{
				if (child->lit == target)
				{
					found = true;
					result = add(child, ds, index + 1, max_index);
					break;
				}
			}
			if (!found)
			{
				literal_node *new_node = new literal_node(n, target, false);
				n->children.push_back(new_node);
				result = add(new_node, ds, index + 1, max_index);
				count++;
			}

			return result;
		}

		void clear(literal_node *n)
		{
			for (auto& child : n->children)
			{
				clear(child);
			}
			n->children.clear();
			delete n;
		}

		int count;

	public:

		decision_string_collection() : count(0), string_id(0)
		{
			root = new literal_node();
		}

		virtual ~decision_string_collection()
		{
			if (root != nullptr)
			{
				clear(root);
				root = nullptr;
			}
			count = 0;
		}

		void clear()
		{
			string_id = 0;
			clear(root);
			root = new literal_node();
		}

		bool find_strings(decision_string& ds, std::list<literal_node *>& found_strings)
		{
			if (!ds.sorted)
				ds.sort();
			bool result;
			result = find_strings(root, ds, 0, ds.size(), found_strings);
			return result;
		}

		int add(decision_string& ds)
		{
			if (!ds.sorted)
				ds.sort();
			int sid = 0;
			sid = add(root, ds, 0, ds.size());
			return sid;
		}
		
		int get_count()
		{
			return count;
		}

		void self_test(std::list<std::string>& results)
		{

			decision_string rule1("ABC");
			decision_string rule2("A!BF");
			decision_string rule3("CD");
			decision_string rule4("!ABD");
			decision_string rule5("!B!E");

			add(rule1);
			add(rule2);
			add(rule3);
			add(rule4);
			add(rule5);

			decision_string test1("AB!CD");
			decision_string test2("AB*CD");
			decision_string test3("AB*CE*");

			std::list<literal_node *> fn1, fn2, fn3, fn4, fn5, fn6, fn7, fn8, fn9;

			if (!find_strings(rule1, fn1)) 
				results.push_back("rule1 invalid");

			if (!find_strings(rule2, fn2))
				results.push_back("rule2 invalid");

			if (!find_strings(rule3, fn3))
				results.push_back("rule2 invalid");

			if (!find_strings(rule3, fn3))
				results.push_back("rule2 invalid");

			if (!find_strings(rule4, fn4))
				results.push_back("rule4 invalid");

			if (!find_strings(rule5, fn5))
				results.push_back("rule5 invalid");

			// now, should be able to find 2 & 3 but not find 1
			if (find_strings(test1, fn6))
				results.push_back("test1 invalid");

			if (!find_strings(test2, fn7))
				results.push_back("test2 invalid");

			if (!find_strings(test3, fn8))
				results.push_back("test3 invalid");

		}
	};

}
